Paper 2023/466

Don't be Dense: Efficient Keyword PIR for Sparse Databases

Sarvar Patel, Google (United States)
Joon Young Seo, Google (United States)
Kevin Yeo, Google (United States), Columbia University
Abstract

In this paper, we introduce $\mathsf{SparsePIR}$, a single-server keyword private information retrieval (PIR) construction that enables querying over sparse databases. At its core, $\mathsf{SparsePIR}$ is based on a novel encoding algorithm that encodes sparse database entries as linear combinations while being compatible with important PIR optimizations including recursion. $\mathsf{SparsePIR}$ achieves response overhead that is half of state-of-the art keyword PIR schemes without requiring long term client storage of linear sized mappings. We also introduce two variants, $\mathsf{SparsePIR}^g$ and $\mathsf{SparsePIR}^c$, that further reduces the size of the serving database at the cost of increased encoding time and small additional client storage, respectively. Our frameworks enable performing keyword PIR with, essentially, the same costs as standard PIR. Finally, we also show that $\mathsf{SparsePIR}$ may be used to build batch keyword PIR with halved response overhead without any client mappings.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2023
Keywords
Private Information RetrievalPIRkeyword PIRbatch PIR
Contact author(s)
sarvar @ google com
jyseo @ google com
kwlyeo @ google com
History
2023-06-14: revised
2023-03-30: received
See all versions
Short URL
https://ia.cr/2023/466
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/466,
      author = {Sarvar Patel and Joon Young Seo and Kevin Yeo},
      title = {Don't be Dense: Efficient Keyword {PIR} for Sparse Databases},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/466},
      year = {2023},
      url = {https://eprint.iacr.org/2023/466}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.